package 中等.贪心思想;

/**
 * 给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。
 * 你是否可以从 nums 中选出 n 个 不相交 的子数组，使得第 i 个子数组与
 * groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 
 * 个子数组在 nums 中出现的位置在第 i 个子数组前面。（也就是说，这些
 * 子数组在 nums 中出现的顺序需要与 groups 顺序相同）
 * 如果你可以找出这样的 n 个子数组，请你返回 true ，否则返回 false 。
 * 如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子
 * 数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/form-array-by-concatenating-subarrays-of-another-array
 */
public class 通过连接另一个数组的子数组得到一个数组_1764 {

    public static void main(String[] args) {

        System.out.println(new 通过连接另一个数组的子数组得到一个数组_1764()
                .canChoose(new int[][]{{1, -1, -1}, {3, -2, 0}},
                        new int[]{1, -1, 0, 1, -1, -1, 3, -2, 0}));

    }

    private int[][] groups_;
    private int[] nums_;

    /**
     * 贪心思想+双指针
     * 如果当前 nums[i,i+group.length-1] 和 group[gIdx] 相匹配
     * 即使后面的 nums[i+1,i+group.length-1] 也和  group[gIdx] 相匹配,
     * 优先使用较小的索引 i 进行匹配，因为 [i,end] 越长，留给后面
     * 匹配的 group 机会越大
     */
    public boolean canChoose(int[][] groups, int[] nums) {
        groups_ = groups;
        nums_ = nums;

        return dfs(0, 0);
    }

    private boolean dfs(int gIdx, int nIdx) {
        if (gIdx == groups_.length) return true;
        if (nIdx >= nums_.length) return false;

        boolean flag = false;
        int[] group = groups_[gIdx];
        for (int i = nIdx; i < nums_.length - group.length + 1; i++) {
            int tempI = i;
            boolean like = true;
            for (int j = 0; j < group.length; j++, tempI++) {
                if (group[j] != nums_[tempI]) {
                    like = false;
                    break;
                }
            }
            if (like) {
                flag = flag || dfs(gIdx + 1, i + group.length);
                break;
            }
        }
        return flag;
    }

}
